/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Admin
 * Date: 2022-05-25
 * Time: 11:12
 */

public class TestHeap {
    public int elem[];
    public int UsedSize;

    public TestHeap() {
        this.elem = new int[10];
    }

    /**
     * 创建大根堆
     *
     * @param array
     */
    public void createHeap(int[] array) {
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            UsedSize++;
        }

        for (int i = (UsedSize - 1 - 1) / 2; i >= 0; i--) {
            shiftDown(i,UsedSize);
        }
    }

    public void shiftDown(int parent,int end) {
        int index = parent * 2 + 1;

        while (index < end) {
            if (index != end - 1 && elem[index] < elem[index + 1]) {
                index++;
            }

            if (elem[index] > elem[parent]) {
                int tmp = elem[index];
                elem[index] = elem[parent];
                elem[parent] = tmp;
                parent = index;
                index = parent * 2 + 1;
            } else {
                break;
            }
        }
    }

    public void heapSort() {
        int end = UsedSize-1;

        while(end > 0) {
            int tmp = elem[0];
            elem[0] = elem[end];
            elem[end] = tmp;
            shiftDown(0,end);
            end--;
        }
    }
}